\title{CS531 Programming Assignment 3: SuDoKu}
\author{
        Michael Lam, Xu Hu \\
        EECS, Oregon State University\\
        %\email{}
        %\and
}
\documentclass[12pt]{article}

%\usepackage{multirow}
\usepackage[lofdepth,lotdepth]{subfig}
\usepackage{float}
\usepackage{epstopdf}
\usepackage{algorithmic}
\usepackage{algorithm}
\usepackage[english]{babel}
\usepackage{graphicx}
%\usepackage{subfig}
\usepackage{amsmath}
%\usepackage{hyperref}
%\hypersetup{
%    colorlinks,%
%    citecolor=green,%
%    filecolor=magenta,%
%    linkcolor=red,%
%    urlcolor=cyan
%}

%\underset{x}{\operatorname{argmax}}
%\underset{x}{\operatorname{argmin}}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\argmax}{arg\,max}

\begin{document}
\maketitle

\begin{abstract}
In this assignment we design, implement and discuss constraint propagation and backtracking search algorithms in order to solve a specific constraint satisfication problem, SuDoKu. 
\end{abstract}

% -------------------------------------------------
\section{Introduction}

SuDoKu is a puzzle and constraint satisfication problem in which every unit (i.e. row, column or box) is an all-diff constraint. Each of the 81 squares can be represented as a variable on a domain of $\{1, 2, 3, ..., 9\}$. SuDoKu may be solved by backtracking search with constraint propagation.

A SuDoKu problem can be classified as easy, medium, hard or evil depending on what rules are required (and also if backtracking search is required) to solve the puzzle. We performed experiments to demonstrate that indeed, harder problems require more rules in order to solve them without backtracking. It turns out that the naked double and triple rules are effective enough to solve most problems without backtracking. However, we also show that backtracking is required to solve certain problems, and that backtracking search solves every puzzle.

Finally, we demonstrate that using the heuristic of picking a variable randomly for assignment during backtracking search rather than the most constrained variable yields a higher number of backtracking. Therefore the heuristic of picking the most constrained variable is effective in reducing the number of backtrackings.

\input{1_Algorithm}
\input{Experiments}
\input{Discussion}

\bibliographystyle{plain}
\bibliography{ref}

\end{document}
This is never printed
